/**
 * @param {string} s
 * @return {number}
 */
var minCut = function(s) {
  if(isPalindrome(s, 0, s.length - 1)) return 0
  const queue = [s]
  const visited = {
    [s]: true
  }
  let ans = 1
  while(queue.length > 0) {
    let len = queue.length
    for(let i = 0; i < len; i++) {
      let str = queue.shift()
      for(let j = 0; j < str.length - 1; j++) {
        let tempS = str.substring(j + 1)
        let flg = isPalindrome(str, 0, j)
        if(!flg) continue
        if(flg && isPalindrome(str, j+1, str.length - 1)) return ans
        if(flg && !visited[tempS]) {
          visited[tempS] = true
          queue.push(tempS)
        }
      }
    }
    ans++
  }
  return ans
};
var isPalindrome = function(s, left, right) {
  while(left <= right) {
      if(s[left] !== s[right]) {
          return false
      }
      left++
      right--
  }
  return true
}
console.log(minCut("leet"));